#include <vector>
using namespace std;
// 找到中间位置 判断左侧是否有序
int search(vector<int> &nums, int target) {
  int left = 0;
  int right = nums.size() - 1;
  int mid = -1;
  while (left <= right) {
    mid = (left + right) / 2;
    if (nums[mid] == target) {
      return mid;
    }
    if (nums[left] <= nums[mid]) {
      // 左侧有序
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // 右侧有序
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}